package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class 力扣56_合并区间 {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        System.out.println(Arrays.deepToString(merge(intervals)));
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 4}, {0, 4}})));
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 4}, {2, 3}})));
    }

    /**
     * 依次和前面的数组比较
     * 首先根据 数组2[0] 和 数组1[1] 比较 是否连续  如果不连续 拆分
     * 如果连续 再根据 数组2[1] 和 数组1[1] 比较 是否包围 如果不包围 将两个数组合并 数组1[1] = 数组2[1] 如果包围 continue
     * 二 [1,4] [5,6]    不连续
     * 一 [1,4] [2,6]    连续
     * 三 [1,4] [2,3]    包围
     */
    static int[][] merge(int[][] intervals) {
        // 先根据数组第一个数字排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        ArrayList<Integer[]> mergeList = new ArrayList<>();
        int[] pre = intervals[0];   // 第一个数组
        // 从第二个数组开始遍历
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            // 先判断 当前数组首个数字是否大于前面的数组最后的数字 成立 说明不连续
            if (cur[0] > pre[1]) {
                mergeList.add(new Integer[]{pre[0], pre[1]});
                pre = cur;
            }
            // 如果 连续 根据 第二个数字 判断是否被包围  被包围跳过当前整个数组 否则更新之前数组的第二个数组
            if (cur[1] > pre[1]) {
                pre[1] = cur[1];
            } else {
                // 被包围了 跳过 不处理
            }
        }

        // 将最后一个数据加入
        mergeList.add(new Integer[]{pre[0], pre[1]});

        return mergeList.toArray(new int[mergeList.size()][]);
    }

}
